package com.TestDemo.Test2;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/14/22:10
 * @Description:
 * @Target:
 */
class MyLinkedList {

    class Node {  // 节点
        int val; // 值
        Node next; // 下一个链表

        Node(int val) {  // 链表对象构造器
            this.val = val;
        }
    }

    int size;
    Node head;
    public MyLinkedList() {
        this.size = 0;
        this.head = null;
    }

    public int get(int index) {
        if(index < 0 || index > size || head == null){  // 不满足的条件
            return -1;
        }

        Node temp = this.head;  // 从头节点开始

        for(int i = 0; i < index; i++){
            temp = temp.next;   // 不读指向下一个节点,temp是节点
        }

        return temp.val;   // 节点的值
    }

    public void addAtHead(int val) {
        Node node = new Node(val);
        node.next = this.head;  // 这个节点的next指向初始化或者后来加的头对象的
        this.head = node;
        size++;
    }

    public void addAtTail(int val) {
        // 先判断是不是空链表
        if(size==0){
            this.head = new Node(val);
            head.next = null;
            size++;
        }else{
            // 从头开始找,找到末尾节点
            Node temp = this.head;
            while(temp.next!=null){
                temp = temp.next;
            }
            // 现在末尾也有了,新加的节点新建
            Node tail = new Node(val);
            tail.next = null;
            temp.next = tail;
            size++;
        }
    }

    public void addAtIndex(int index, int val) {
        // >size 中断
        if(index > this.size){return;}

        // <=0 头增
        if(index <= 0){
            addAtHead(val);
            return;
        }

        // ==size 尾增
        if(index == this.size){
            addAtTail(val);
            return;
        }

        // 正常加 先找到加的位置
        Node temp = this.head;   // 先抓到头
        for(int i = 0; i < index-1;i++){ // 依据坐标进行for寻找
            temp = temp.next;
        }

        Node newNode = new Node(val);  // 新建一个

        newNode.next = temp.next;  // 先获取到下一节点的坐标
        temp.next = newNode;   // 原节点next指向现节点
        size++;

    }

    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){return;}
        // 如果index是头节点:::要判断是不是只有头节点
        if(index==0){

            if(size!=1){   // 不仅仅头节点
                Node temp = this.head.next;
                this.head = temp;
                size--;
                return;
            }else{   // 仅仅头节点
                this.head = null;
                size--;
                return;
            }
        }
            // 正常删除  --- 找位置 ---目标前节点的next指向目标后节点 --front(next->back)--target--back-----
            Node temp = this.head;
            for(int i = 0;i < index-1;i++){  // 找到目标前一个节点
                temp = temp.next;
            }

            Node deleteNode = temp.next;
            temp.next = deleteNode.next;
            size--;

        }

}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 *//**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */
